home *** CD-ROM | disk | FTP | other *** search
/ PD Collection CD 1 / PD Collection CD 1.iso / textual / tex / files / !tex / TeXsource / commontex / c / heap < prev    next >
Encoding:
Text File  |  1988-04-18  |  6.3 KB  |  239 lines
  1. /*
  2.  *    Copyright 1986, 1987 Pat Joseph Monardo. All rights reserved.
  3.  *    Copying of this file is granted according to the provisions 
  4.  *    specified in the file COPYING which must accompany this file.
  5.  */
  6.  
  7.  
  8. /*
  9.  *              heap.c
  10.  */
  11.  
  12. #include "tex.h"
  13. #include "eq.h"
  14. #include "arith.h"
  15. #include "box.h"
  16. #include "evalstack.h"
  17. #include "par.h"
  18. #include "page.h"
  19. #include "print.h"
  20. #include "error.h"
  21. #include "heap.h"
  22.  
  23. mword   mem[MEM_MAX-MEM_MIN+1];
  24. ptr             mem_end;
  25. ptr             lo_mem_max;
  26. ptr             hi_mem_min;
  27. ptr             avail;
  28. int             dyn_used;
  29. ptr             rover;
  30. int             var_used;
  31. int             max_var_used;
  32. ptr             temp_ptr;
  33.  
  34. ptr
  35. get_avail ()
  36. {
  37.         ptr             p;
  38.  
  39.         p = avail;
  40.         if (p != NULL)
  41.                 avail = link(avail);
  42.         else if (mem_end < MEM_MAX) {
  43.                 incr(mem_end);
  44.                 p = mem_end;
  45.         } else {
  46.                 decr(hi_mem_min);
  47.                 p = hi_mem_min;
  48.                 if (hi_mem_min <= lo_mem_max) {
  49.                         runaway();
  50.                         overflow("main memory size", MEM_MAX - MEM_MIN);
  51.                 }
  52.         }
  53.         link(p) = NULL;
  54. #ifdef STAT
  55.         incr(dyn_used);
  56. #endif
  57.         return p;
  58. }
  59.  
  60. ptr
  61. get_node (s)
  62.         int             s;
  63. {
  64.         ptr             p;
  65.         ptr             q;
  66.         int             r;
  67.         int             t;
  68.  
  69. restart:
  70.         p = rover;
  71.         do {
  72.                 q = p + node_size(p);
  73.                 while (is_empty(q)) {
  74.                         t = rlink(q);
  75.                         if (q == rover)
  76.                                 rover = t;
  77.                         llink(t) = llink(q);
  78.                         rlink(llink(q)) = t;
  79.                         q += node_size(q);
  80.                 }
  81.                 r = q - s;
  82.                 if (r > (int) p + 1)  {
  83.                         node_size(p) = r - p;
  84.                         rover = p;
  85.                         goto found;
  86.                 }
  87.                 if (r == p && (rlink(p) != p)) {/*DIFF*/
  88.                         rover = rlink(p);
  89.                         t = llink(p);
  90.                         llink(rover) = t;
  91.                         rlink(t) = rover;
  92.                         goto found;
  93.                 }
  94.                 node_size(p) = q - p;
  95.                 p = rlink(p);
  96.         } while (p != rover);
  97.         if (s == 010000000000)
  98.                 return MAX_HALFWORD;
  99.         if (lo_mem_max + 2 < hi_mem_min && 
  100.                 lo_mem_max + 2 <= MEM_BOT + MAX_HALFWORD) {
  101.                 if (lo_mem_max + 1000 < hi_mem_min)
  102.                         t = lo_mem_max + 1000;
  103.                 else t = (lo_mem_max + hi_mem_min + 2) / 2;
  104.                 p = llink(rover);
  105.                 q = lo_mem_max;
  106.                 rlink(p) = q;
  107.                 llink(rover) = q;
  108.                 if (t > MEM_BOT + MAX_HALFWORD)
  109.                         t = MEM_BOT + MAX_HALFWORD;
  110.                 rlink(q) = rover;
  111.                 llink(q) = p;
  112.                 link(q) = EMPTY_FLAG;
  113.                 node_size(q) = t - lo_mem_max;
  114.                 lo_mem_max = t;
  115.                 link(lo_mem_max) = NULL;
  116.                 info(lo_mem_max) = NULL; 
  117.                 rover = q;
  118.                 goto restart;
  119.         }
  120.         overflow("main memory size", MEM_MAX + 1 - MEM_MIN);
  121.  
  122. found:
  123.         link(r) = NULL;
  124. #ifdef STAT
  125.         var_used += s;
  126. #endif
  127.         return r;
  128. }
  129.  
  130. free_node (p, s)
  131.         ptr             p;
  132.         hword   s;
  133. {
  134.         ptr             q;
  135.  
  136.         node_size(p) = s;
  137.         link(p) = EMPTY_FLAG;
  138.         q = llink(rover);
  139.         llink(p) = q;
  140.         rlink(p) = rover;
  141.         llink(rover) = p;
  142.         rlink(q) = p;
  143. #ifdef STAT
  144.         var_used -= s;
  145. #endif
  146. }
  147.  
  148. init_mem ()
  149. {
  150.         int             k;
  151.         
  152. #ifdef INIT
  153.         for (k = MEM_BOT + 1; k <= LO_MEM_STAT_MAX; k++)
  154.                 mem[k].sc = 0;
  155.         for (k = MEM_BOT; k <= LO_MEM_STAT_MAX; k += GLUE_SPEC_SIZE) {
  156.                 glue_ref_count(k) = NULL + 1;
  157.                 stretch_order(k) = NORMAL;
  158.                 shrink_order(k) = NORMAL;
  159.         }
  160.         stretch(fil_glue) = UNITY;
  161.         stretch_order(fil_glue) = FIL;
  162.         stretch(fill_glue) = UNITY;
  163.         stretch_order(fill_glue) = FILL;
  164.         stretch(ss_glue) = UNITY;
  165.         stretch_order(ss_glue) = FIL;
  166.         shrink(ss_glue) = UNITY;
  167.         shrink_order(ss_glue) = FIL;
  168.         stretch(fil_neg_glue) = -UNITY;
  169.         stretch_order(fil_neg_glue) = FIL;
  170.         
  171.         rover = LO_MEM_STAT_MAX + 1;
  172.         link(rover) = EMPTY_FLAG;
  173.         node_size(rover) = 1000;
  174.         llink(rover) = rover;
  175.         rlink(rover) = rover;
  176.  
  177.         lo_mem_max = rover + 1000;
  178.         link(lo_mem_max) = NULL;
  179.         info(lo_mem_max) = NULL;
  180.         for (k = HI_MEM_STAT_MIN; k <= MEM_TOP; incr(k))
  181.                 mem[k] = mem[lo_mem_max];
  182.  
  183.         link(end_span) = MAX_QUARTERWORD + 1;
  184.         info(end_span) = NULL;
  185.         type(last_active) = HYPHENATED;
  186.         subtype(last_active) = 0;
  187.         line_number(last_active) = MAX_HALFWORD;
  188.         type(page_ins_head) = SPLIT_UP;
  189.         subtype(page_ins_head) = qi(255);
  190.         link(page_ins_head) = page_ins_head;
  191.         type(page_head) = GLUE_NODE;
  192.         subtype(page_head) = NORMAL;
  193.  
  194.         avail = NULL;
  195.         mem_end = MEM_TOP;
  196.         hi_mem_min = HI_MEM_STAT_MIN;
  197.         var_used = LO_MEM_STAT_MAX + 1 - MEM_BOT;
  198.         dyn_used = HI_MEM_STAT_USAGE;
  199. #endif
  200. }
  201.  
  202. sort_avail()
  203. {
  204.         ptr             p;
  205.         ptr             q;
  206.         ptr             r;
  207.         ptr             old_rover;
  208.  
  209. #ifdef INIT
  210.         get_node(010000000000);
  211.         p = rlink(rover);
  212.         rlink(rover) = MAX_HALFWORD;
  213.         old_rover = rover;
  214.         while (p != old_rover) {
  215.                 if (p < rover) {
  216.                         q = p;
  217.                         p = rlink(q);
  218.                         rlink(q) = rover;
  219.                         rover = q;
  220.                 } else {
  221.                         q = rover;
  222.                         while (rlink(q) < p)
  223.                                 q = rlink(q);
  224.                         r = rlink(p);
  225.                         rlink(p) = rlink(q);
  226.                         rlink(q) = p;
  227.                         p = r;
  228.                 }
  229.         }
  230.         p = rover;
  231.         while (rlink(p) != MAX_HALFWORD) {
  232.                 llink(rlink(p)) = p;
  233.                 p = rlink(p);
  234.         }
  235.         rlink(p) = rover;
  236.         llink(rover) = p;
  237. #endif
  238. }
  239.